
public class AlgoritmulBellman_Ford 
{
	private GrafOrientat graf;
	private int n , inf = 999999999;
	private Muchie [] e;
	private int [] d, p;
	
	public AlgoritmulBellman_Ford(GrafOrientat graf)
	{
		this.graf = graf;
		n = graf.getNrVarfuri();
		e = graf.getListaInc();
		d = new int[n];
		p = new int [n];
	}
	
	private int min(int k)
	{
		int m = graf.getNIncidenta();
		int min = inf , poz = -1;
		for(int i=0;i<m;i++)
		{
			if(e[i].to == k)
				if(min > e[i].val)
				{
					min = e[i].val;
					poz = i;
				}
		}
		return poz;
	}
	
	private void alg(int s)
	{
		d[s] = 0;
		p[s] = 0;
		
		for(int i=0;i<n;i++)
			if(i != s)
			{
				d[i] = inf;
				p[i] = 0;
			}
		
		int [] d2 = new int[n];
		boolean ok;
		do
		{
			for(int i=0;i<n;i++)
				d2[i] = d[i];
			ok = true;
			for(int i=0;i<n;i++)
			{
				int x = min(i);
				if(x != -1)
				{
					if(d2[e[x].from] + e[x].val < d2[e[x].to])
					{
						d[e[x].to] = d2[e[x].from]+e[x].val;
						p[e[x].to] = e[x].from;
						ok = false;
					}
				}
			}
		}
		while(ok == false);
	}
	
	public String getRezultat(int s , int k)
	{
		alg(s);
		String str = " "+k;
		int k2 = k;
		System.out.println("pk="+p[k]);
		while(p[k] != s)
		{
			str = str+" "+ String.valueOf(p[k]);
			k = p[k];
		}
		str = str + " " + s;
		
		String s2 = new String();
		for(int i=str.length()-1;i>=0;i--)
			s2 = s2+str.charAt(i);
		
		return s2+"\n Costul total este "+d[k2];
	}
}
